package com.ankicoo.practice.caculate.GaussElomination;

import java.math.BigDecimal;
import java.math.RoundingMode;
import java.util.Arrays;
import java.util.List;

/**
 * 【高斯消元法】
 *  基本思想是：通过一系列的加减消元运算，直到得到类似 kx=b 的式子，然后逐一回代求解 x 向量
 */
public class GaussEliminationMethod {

    public static void main(String[] args) {
        BigDecimal[][] A = {
                {BigDecimal.valueOf(1), BigDecimal.valueOf(-1), BigDecimal.valueOf(3), BigDecimal.valueOf(4)},
                {BigDecimal.valueOf(2), BigDecimal.valueOf(5), BigDecimal.valueOf(8), BigDecimal.valueOf(9)},
                {BigDecimal.valueOf(1), BigDecimal.valueOf(5), BigDecimal.valueOf(2), BigDecimal.valueOf(1)},
                {BigDecimal.valueOf(6), BigDecimal.valueOf(6), BigDecimal.valueOf(8), BigDecimal.valueOf(1)}};

        BigDecimal[] B = {BigDecimal.valueOf(5),BigDecimal.valueOf(5),BigDecimal.valueOf(5),BigDecimal.valueOf(5)};
        long x = System.currentTimeMillis();
        System.out.println(x);
        int i = 100000;
        while (i>0){
            calc(A, B);
            i--;
        }
        long y = System.currentTimeMillis();
        System.out.println(y-x);

    }

    /**
     * 已知：常数多列矩阵A 常数单列矩阵B 及未知数单列矩阵X 且三个矩阵满足条件 AX=B
     * 通过运算使增广矩阵（A,B）化为阶梯矩阵
     * 再进行消元计算 得到结果矩阵X
     * @param A 矩阵A
     * @param B 矩阵B
     * @return 矩阵X
     */
    public static BigDecimal[] calc(BigDecimal[][] A, BigDecimal[] B){
        int row = A.length;
        enlarge2LadderMatrix(A,B);

        System.out.println(Arrays.deepToString(A));
        System.out.println("----------------------");
        System.out.println(Arrays.deepToString(B));

        return recursiveSolution(A, B);
    }

    /**
     * 将矩阵转换为阶梯矩阵
     * @param A 矩阵A
     */
    private static void enlarge2LadderMatrix(BigDecimal[][] A, BigDecimal[] B){
        int row = A.length;
        int col = row>0 ? A[0].length : 0;
        for (int i = 1; i < row; i++) {
            for (int j = 0; j < i; j++) {
                if (A[i][j].compareTo(BigDecimal.ZERO)!=0){
                    BigDecimal currentVal = A[i][j];
                    BigDecimal targetVal = A[j][j];
                    B[i] = B[i].multiply(targetVal).subtract(B[j].multiply(currentVal));
                    for (int k = 0; k < col; k++) {
                        A[i][k] = A[i][k].multiply(targetVal).subtract(A[j][k].multiply(currentVal)) ;
                    }
                }
            }
        }
    }


    private static BigDecimal[] recursiveSolution(BigDecimal[][] A, BigDecimal[] B){
        int length = B.length;
        BigDecimal[] X = new BigDecimal[B.length];
        for (int i = length-1; i >= 0; i--) {
            BigDecimal temp  = B[i];
            for (int j = i+1; j < length; j++) {
                temp = temp.subtract(A[i][j].multiply(X[j]));
            }
            X[i]   = temp.divide(A[i][i],RoundingMode.HALF_UP);
        }
        return X;
    }
}
